﻿#include "QuadTree.h"

const float offset = 1.15f;
const float maxextra = -1.f;

//check if rect1 is inside rect2
bool inside(const RECT &rect1,const RECT &rect2)
{
	//if ((rect1.top - rect2.top >= maxextra) && (rect1.left - rect2.left >= maxextra) && (rect1.right - rect2.right <= -maxextra) && (rect1.bottom - rect2.bottom <= -maxextra))
	if ((rect1.top >= rect2.top) && (rect1.left >= rect2.left) && (rect1.right <= rect2.right) && (rect1.bottom <= rect2.bottom))
		return true;
	else return false;
}

int QuadNode::CheckRect(RECT rect)
{
	
	RECT childRect;
	int k=0;
	for (int i=1;i<=4;i++)
	{
		childRect = calChildRect(i);
		//if (inside(rect,childRect))
		if (inside(rect,childRect))
			return i;
	}
	
	return k;
}

QuadNode::QuadNode(float x,float y, int width, int height)
{
	_nodeRect = RECT();
	_nodeRect.left = x;
	_nodeRect.right = x + width;
	_nodeRect.top = y;
	_nodeRect.bottom = y + height;

	float newW = width * offset;
	float newH = height * offset;

	float centerX = _nodeRect.left + width / 2;
	float centerY = _nodeRect.top + height / 2;

	_looseRect = RECT();

	_looseRect.left = centerX - newW/2;
	_looseRect.right = _looseRect.left + newW;
	_looseRect.top = centerY - newH/2;
	_looseRect.bottom = _looseRect.top + newH;

	
	_isDivided = false;

	_maxHeight = 20;
	
}

void QuadNode::AddObject(GObject *object, int Height)
{
	RECT rect = object->getRect();
	int pos = this->CheckRect(rect);

	float nodeWidth = this->getLooseRect().right - this->getLooseRect().left;
	float nodeHeight = this->getLooseRect().bottom - this->getLooseRect().top;
	float tWidth = rect.right - rect.left;
	float tHeight = rect.bottom - rect.top;

	//object belongs to current node
	if (pos == 0 || tWidth >= 0.25f*nodeWidth || tHeight >= 0.25f*nodeHeight || Height >= _maxHeight)
	{
		this->_objectList.insert(object);
		return;
	}
	//subdivide
	else
	{
		//this is a leaf node
		if (!_isDivided)
		{
			//_nodeList = (QuadNode**)malloc(4*sizeof(QuadNode*));
			_nodeList = new QuadNode*[4];

			if (!_nodeList)
			{
				MessageBox(NULL,"alloc failed","error!",MB_OK);
				return;
			}
			float midX = (_nodeRect.right + _nodeRect.left)/2;//_x + _width/2;
			float midY = (_nodeRect.top + _nodeRect.bottom)/2;//_y + _height/2;
			int halfw = (_nodeRect.right - _nodeRect.left)/2;//_width/2;
			int halfh = (_nodeRect.bottom - _nodeRect.top)/2;//_height/2;
			_nodeList[TL-1] = new QuadNode(_nodeRect.left,_nodeRect.top,halfw,halfh);
			_nodeList[TR-1] = new QuadNode(midX,_nodeRect.top,halfw,halfh);
			_nodeList[BR-1] = new QuadNode(midX,midY,halfw,halfh);
			_nodeList[BL-1] = new QuadNode(_nodeRect.left,midY,halfw,halfh);

			_isDivided = true;
		}

		//add object to approtiate child node
		//if (_nodeList[pos-1])
			_nodeList[pos-1]->AddObject(object,Height+1);
	}
}

void QuadNode::removeObject(GObject* object)
{
	this->_objectList.erase(object);
}

void QuadNode::free()
{
	if (!this->_nodeList)
	{
		for (int i=0;i<4;i++)
			if (this->_nodeList[i])
			{
				this->_nodeList[i]->free();
				delete this->_nodeList[i];
			}
		delete[] _nodeList;
	}
}

std::set<GObject*> QuadNode::getObjectList()
{
	return this->_objectList;
}

std::set<GObject*> QuadNode::getAllObjectList()
{
	std::set<GObject*> contentList = this->getObjectList();
	if (!_isDivided)
		return contentList;
	else
	{
		std::set<GObject*> objList = std::set<GObject*>();
		std::set<GObject*> tList;
		for (int i=0;i<4;i++)
		{
			tList = _nodeList[i]->getAllObjectList();
			/*objList.insert(objList.end(),tList.begin(),tList.end());
			objList.insert(objList.end(),contentList.begin(),contentList.end());*/
			objList.insert(tList.begin(),tList.end());
			objList.insert(contentList.begin(),contentList.end());
		}
		return objList;
	}
}

bool QuadNode::isDivided()
{
	return _isDivided;
}

QuadNode** QuadNode::getNodeList()
{
	return this->_nodeList;
}

bool QuadNode::isBelong(GObject* object)
{
	if (this->CheckRect(object->getRect()) == 0)
		return true;
	else return false;
}

void QuadNode::setObjectList(std::set<GObject*> newList)
{
	_objectList = newList;
}

int QuadNode::countObject()
{
	int k = this->_objectList.size();
	if (this->isDivided())
		for (int i=0;i<4;i++)
			k += this->_nodeList[i]->countObject();
	return k;
}

QuadTree::QuadTree(void)
{
}

QuadTree::QuadTree(int width, int height)
{
	this->_root = new QuadNode(0,0,width,height);
}


QuadTree::~QuadTree(void)
{
	_root->free();
}

void QuadTree::add(GObject *object)
{
	_root->AddObject(object,0); 
}

QuadNode* QuadNode::getNode(const RECT &rect)
{
	int index;
	for (int i=1;i<=4;i++)
	{
		//kiểm tra xem vùng rect có thuộc 1 trong 4 node con ko
		index = this->CheckRect(rect);
		//nếu đây là node cần tìm
		if (index == 0)
			return this;
		//đệ quy xuống node con
		else return this->_nodeList[index];
	}
}

std::set<GObject*> QuadNode::getCollidableObject(const RECT &rect)		//lấy tất cả các obj trong các node có rect có phần trùng với tham số rect
{
	std::set<GObject*> objList = std::set<GObject*>();
	std::set<GObject*> tList = std::set<GObject*>();
	std::set<GObject*> currentList = this->getObjectList();
	if (!_isDivided)
	{
		std::set<GObject*> rlist = std::set<GObject*>();
		for (std::set<GObject*>::iterator it = currentList.begin(); it != currentList.end();it++)
			if (isIntersect(rect,(*it)->getRect()))
				rlist.insert((*it));
		return rlist;
	}
	for (int i=0;i<4;i++)
	{
		if (this->isIntersect(rect,this->_nodeList[i]->getLooseRect()))
		{
			tList = this->_nodeList[i]->getCollidableObject(rect);
			//objList.insert(objList.end(),tList.begin(),tList.end());
			objList.insert(tList.begin(),tList.end());
		}
	}

	std::set<GObject*> rlist = std::set<GObject*>();
	for (std::set<GObject*>::iterator it = currentList.begin(); it != currentList.end();it++)
		if (isIntersect(rect,(*it)->getRect()))
			rlist.insert((*it));
	objList.insert(rlist.begin(),rlist.end());
	return objList;
}

QuadNode::~QuadNode(void)
{
	for (int i=0;i<4;i++)
			delete this->_nodeList[i];
	delete[] this->_nodeList;
	//free(this->_nodeList);
}

bool QuadNode::isIntersect(RECT rect1, RECT rect2)
{
	if (rect1.top > rect2.bottom || rect1.bottom < rect2.top || rect1.left > rect2.right || rect1.right < rect2.left)
		return false;
	else return true;
}

RECT QuadNode::calChildRect(int ChildIndex)
{
	RECT rect = RECT();
	float width = _nodeRect.right - _nodeRect.left;
	float height = _nodeRect.bottom - _nodeRect.top;

	float tW = width/2;
	float tH = height/2;

	float newW = tW * offset;
	float newH = tH * offset;

	float centerX, centerY;

	
	switch (ChildIndex){
	case TL:
		{
			centerX = _nodeRect.left + tW/2;
			centerY = _nodeRect.top + tH/2;
			break;
		}
	case TR:
		{
			centerX = _nodeRect.left + tW + tW/2;
			centerY = _nodeRect.top + tH/2;
			break;
		}
	case BR:
		{
			centerX = _nodeRect.left + tW + tW/2;
			centerY = _nodeRect.top + tH + tH/2;
			break;
		}
	case BL:
		{
			centerX = _nodeRect.left + tW/2;
			centerY = _nodeRect.top + tH + tH/2;
			break;
		}
	}
	rect.left = centerX - newW/2;
	rect.top = centerY - newH/2;
	rect.right = rect.left + newW;
	rect.bottom = rect.top + newH;
	return rect;
}

void QuadNode::setLeaf()
{
	_isDivided = false;
	for (int i=0;i<4;i++)
		delete _nodeList[i];
	delete[] _nodeList;
}

//std::set<GObject*> QuadTree::checkCollision(QuadNode* currentNode, const RECT& rect)
//{
//	std::set<GObject*> updateList = std::set<GObject*>();
//	std::set<GObject*> list= currentNode->getObjectList();
//	std::set<GObject*> tList = std::set<GObject*>();
//	std::set<GObject*> collidableList = std::set<GObject*>();
//
//	/*if (!inside(currentNode->getRect(),rect))
//		return updateList;*/
//	if (!currentNode->isIntersect(currentNode->getRect(),rect))
//		return updateList;
//
//	bool b;
//
//	std::set<GObject*>::iterator it = list.begin();
//
//	try 
//	{
//		while (it != list.end())
//		{
//			if ((*it)->isMovable())
//			{
//				collidableList = currentNode->getCollidableObject((*it)->getRect());
//				for (std::set<GObject*>::iterator it2 = collidableList.begin();it2 != collidableList.end();it2++)
//				{
//					if (_coll.isIntersect((*it)->getRect(),(*it2)->getRect()))
//						_coll.isCollided((MovingObject*)(*it),(*it2));
//				}
//			
//				//b = currentNode->isBelong((*it));
//				b = inside((*it)->getRect(),currentNode->getLooseRect());
//				if (!b)
//				{
//					updateList.insert((*it));
//					list.erase(it++);
//					int count = list.size();
//					/*if (count == 0)
//						break;*/
//				}
//				else it++;
//			}
//			else it++;
//		}
//		currentNode->setObjectList(list);
//	}
//	catch (char *str)
//	{
//	}
//
//	if (!currentNode->isDivided())
//	{
//		
//		return updateList;
//	}
//	else
//	{
//		for (int i=0;i<4;i++)
//		{
//			tList = checkCollision(currentNode->getNodeList()[i],rect);
//			updateList.insert(tList.begin(),tList.end());
//		}
//		return updateList;
//	}
//}

std::set<GObject*> QuadTree::fixTree(QuadNode* currentNode, const RECT& rect)
{
	std::set<GObject*> updateList = std::set<GObject*>();
	std::set<GObject*> list= currentNode->getObjectList();
	std::set<GObject*> tList = std::set<GObject*>();
	std::set<GObject*> collidableList = std::set<GObject*>();

	/*if (!inside(currentNode->getRect(),rect))
		return updateList;*/
	if (!currentNode->isIntersect(currentNode->getRect(),rect))
		return updateList;

	bool b;

	std::set<GObject*>::iterator it = list.begin();

	try 
	{
		while (it != list.end())
		{
			if (true)//((*it)->isMovable())
			{
				/*collidableList = currentNode->getCollidableObject((*it)->getRect());
				for (std::set<GObject*>::iterator it2 = collidableList.begin();it2 != collidableList.end();it2++)
				{
					if (_coll.isIntersect((*it)->getRect(),(*it2)->getRect()))
						_coll.isCollided((MovingObject*)(*it),(*it2));
				}*/
			
				//b = currentNode->isBelong((*it));
				b = inside((*it)->getRect(),currentNode->getLooseRect());
				if (!b)
				{
					updateList.insert((*it));
					list.erase(it++);
					int count = list.size();
					/*if (count == 0)
						break;*/
				}
				else it++;
			}
			else it++;
		}
		currentNode->setObjectList(list);
	}
	catch (char *str)
	{
	}

	if (!currentNode->isDivided())
	{
		
		return updateList;
	}
	else
	{
		for (int i=0;i<4;i++)
		{
			tList = fixTree(currentNode->getNodeList()[i],rect);
			updateList.insert(tList.begin(),tList.end());
		}
		return updateList;
	}
}


void QuadTree::update(std::set<GObject*> updateList)
{
	//std::set<GObject*>::iterator itBegin = updateList.begin();
	//std::set<GObject*>::iterator itEnd = updateList.end();
	int k=updateList.size();
	//if (k == 0) return;
	int i = 0;
	for (std::set<GObject*>::iterator it = updateList.begin(); it != updateList.end(); it ++)
	{
		this->add((*it));
		i++;
	}
	if (i>0)
	{
		int j = i;
	}
}
